//https://leetcode.cn/problems/random-pick-index/description/
//感觉实现的还不是特别好；应该把索引全保存起来，然后再hash%元素个数取余，找到里面的数；
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

class Solution {
public:
    Solution(std::vector<int>& nums) : nums(nums) {
        std::srand(static_cast<unsigned int>(std::time(nullptr)));
    }

    int pick(int target) {
        int count = 0;
        int chosen_index = -1;

        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == target) {
                count++;
                if (std::rand() % count == 0) {
                    chosen_index = i;
                }
            }
        }

        return chosen_index;
    }

private:
    std::vector<int> nums;
};